[ List Latest Comments Only For Pages | Games | Rated Pages | Rated Games | Subjects of Discussion ]
Comments/Ratings for a Single Item
It seems to me that you would need something more than a chess engine to play a very large Chieftain-type game. As Chieftain is a step toward a chess simulation of a wargame, I would think that a wargame AI of some sort might need to be part of the software package. Or is it possible that, by making what is 'combat' in a wargame 'capture by replacement' in the CV, you can actually calculate the moves? For reference, here's the current largest: /play/pbm/play.php?game%3DOverlord%26settings%3DOverlord+Chess+1.0 Because each side moves 8 pieces/turn [of 64 at start], I think the decision tree is so great that one cannot go very deep. Surely you can truncate the search in various ways, but why wouldn't these ways expose the AI to superior human visual/pattern recognition? There are spots in the game where you can make such in-depth calculations for a number of turns, say 4ish complete turns, in a limited area. You cannot make such calculations for the entire board or game, because there are far too many moves of approximately equivalent value to project the gameboard even 2 turns into the future with high accuracy. Until the end, probably, when the pieces are mostly gone.
The techniques you discuss have been tried, but never met with much success in Chess. Part of the reason is hat it woud require a lot of knowledge to com up with positions to strive for, which could be realistically obtained. The only exception is end-game tablebases. There retrograde analysis is used to work back from checkmate positions or winning conversions 9promotions, or the capture of a piece) to create the end-game table. But this is only feasible because the checkmates and conversion are a well-defined goal, so that positions fitting the requirements can easily be exhaustively generated. The search algorithm that currently works best in Chess is recursive nul-move pruning. There you basicaly explore for what one side can do in 1, 2 3, ... moves when you freeze the pieces of the opponent. (Making him do only null moves.) This is a dumb but thourough way to generate 'ideas', i.e. positions that might be reachable from the current position and achieve some favorable objective according to the evaluation function. If this is not possible (to the specified depth) there is no reason to look any further at this branch, but usualy there are som sequences of moves that cannot be ignored by the opponent. Then it wil search for alternatives for the null moves (starting with the last one, in back-tracking version), while at the same time increasing the search depth. Usually a single null move is replaced by 3 normal ply, to make it less likely that any countermeasure the opponent finds to our 'plan' is merely a delaying tactic. (E.g. if on our third ply we could capture his Rook with a Knight that we manouevred in position with our first two ply, we want to be sure that he will not push taking the Rook over the horizon by a counter threat against our Queen that coud be trivially resolved, while his Rook is trapped). Selective search in Chess has always overlooked too many things to be competative. A more sound alternative that does work is reducing the search depth of moves that seem unlikely to be good (so called 'late moves') based on some static creterion, rather than completely pruning their branches. With a fixed reduction the depth to which these branches are searched will continue to improve with deepening at the root, so that if there is a surprise there, you will eventually see it. (While with hard pruning you would be blind to it forever.) Then, if you discover such a reduced move happens to be good after all, you undo the reduction, and search it to full depth. If it is still good at that depth, in becomes the new principal variation. This algorithm can produce significant extra strength if the static criterion for reducing moves is chosen well. (Reducng all non-captures except passer puses seems to be already helpful.) Of course not every game will behave as Chess. But 'late-move reduction' seems a sensible way to reduce the effective branching ratio in games that suffer from a very high branching ration. (Like multiple-move games or games with piece drops.) E.g. in Arimaa moves that move a piece to a position where it could have gone through a shorter path would be good candidates for reduction, or perhaps any move containing backward steps. In drop games you generally reduce drops (as pieces in hand have higher mobility than on the board.) Part of the Arimaa branching factor is of course taken care of by transposition hashing.
Games with multiple moves per turn will seriously bog down most search algorithms. The increased potential of field positions does tend to exponentiate. What can 'assist' these plodders is some form of 'intuitive' step in the depth search? Intuition being the ability to reach conclusions with incomplete information. [Somebody has probably already done all the following, but I merely give them as an example.] Humans(most anyway) look beyond their current move toward a position which often there may not be a clear path. Sometimes this is simply a desire which motivates the play and may actually never be achieved. A programmer might accumulate enough data to create a database of 'favored' field positions which the 'AI' could then use to influence its overall play. Another 'intuitive' leap could be the assumption that a series of turns would involve a specific number of pieces. Focusing the search on a specific series of moves and exchanges involving only these pieces. As the ply depth increase, those pieces of this group which were removed from play would not be replace by others which were earlier discarded(new pieces introduced during the search, whether by promotion or changing sides, might be considered part of this evaluated group). Of course, these groups could not simply be made up of the 'best' pieces on the field. There are many possibilities to these 'intuitive' leaps. Games can be evaluated in a variety of ways. A programmer needs to think beyond the linear progression of turns. Maybe a search engine which works backward('seeing' a future position and attempting to un-create it to the current position).
''Oh, let us never, never doubt/ What nobody is sure about.'' --Hilaire Belloc Good topic and question that has no direct takers here yet [Arimaa being directly related]. Speculate that any ''CV'' can be tweaked toward complications for computers to the extent needed for the period of time, be it 1990s, 2020s or 2040s. Chess is, or ought to be, so much more than programming strong play. Instead of 50% input from information technologists, how much better it would be for input of 10% each from real ''artists'' of painting or sculpture chess-playing Marcel Duchamp, 10% literature of which Chess is extensive, 10% players of specific next-chesses, 10% prolificists content to talk abstractly instead of concretely, 10% mathematicians, 10% sports enthusiasts, 10% moralists on how to reach the wavering millions etc. (Any one of the foregoing specialists could try another mask for a while too: it's not as if one person is one thing only.) But Joe's topic is important, to put in everyday language what the holes, perceived by experts, are in AI for human-human and human-computer competitive purposes; because the holes then becoming associated with mere rules have to be interpretable by players regardless the underlying theory pointing one direction or another.
There have been several discussions on whether a particular game, or particular style of game, is easy or hard to write a decent game-playing program for. There have also been several challenges to design a game computers would have difficulty playing. Ideally, people would have an easy time playing this game. Might as well throw my hat into the ring, even though I don't know anything about computers or programming. I suspect the Chieftain series of games would get progressively more difficult for programmers as the games get larger. And, if not now, certainly at a later stage of development, I think the chesimals games would be rather difficult to program. These are large, multi-move games, where the exact sequence of piece moves in each turn makes a difference, and all moving pieces must start their move within a certain small number of squares from one of the multiple king pieces in the game [a 'command control' rule, as in wargames]. These are the key features of the games. http://www.chessvariants.org/index/msdisplay.php?itemid=MSchieftainchess http://www.chessvariants.org/index/msdisplay.php?itemid=MSchesimals:auto If the preceding is not enough, I have been looking at a hierarchy of leaders for chieftain variants; and at 'open chesimals', multi-unit 'pieces' that may maintain a separation of 1 square between any 2 units of the 'piece'. Do these design features make for a difficult-to-program game?
6 comments displayed
Permalink to the exact comments currently displayed.